This invention is in the field of data security. Embodiments are more specifically directed to the authentication of digital communications using to elliptic curve cryptography (ECC).
Security of data communications is a significant issue for virtually every type of electronic system, ranging from large-scale systems such as supercomputers to the smallest scale systems, such as embedded processors. Indeed, security is becoming the paramount issue for small scale systems such as the sensors and actuators envisioned for deployment in the “Internet of Things” (IoT). These highly distributed IoT objects, which will be implemented in large numbers over a wide range of services and applications, including health, education, resource management, and the like, can be particularly vulnerable to attack and compromise, given their relatively small computational capacity and remote implementation. However, the importance of the functions carried out by a network of these sensors and actuators raises the security stakes.
Further complicating the security challenge for IoT devices is the significant constraints on power consumption placed on these devices. It is contemplated that many of the sensors, actuators, and other IoT nodes will be remotely powered, whether by way of long life batteries, solar cells at the device, or from the wireless communication signal itself. As such, the power budget that can be devoted to computations involved in authentication of communications, among other security functions such as encryption and decryption, can be quite limited.
Various approaches are known in the field of digital data cryptography, such as may be used for data communications, data storage and retrieval, and other applications. In general, the field of cryptography encompasses data encryption and decryption, digital authentication of digital data (e.g., sign/verify schemes), and the like. Public key cryptography, also referred to as asymmetric cryptography, is a commonly used type of cryptography. According to this approach, a public-private pair of “keys”, each key being a block of data or information, are generated according to a particular algorithm. The public and private keys have an inverse relationship with one another based on a generator polynomial, such that the transmitting node secures the communication using one of the keys in the pair, and the receiving node decrypts or verifies the communication using the other key. More specifically, in the data encryption context, a block of data that is encrypted using the public key can be decrypted using the private key; in the authentication context, a digital signature generated using the private key can be verified using the public key. The public and private keys are related to one another via a difficult mathematical problem (commonly referred to as a “trap-door function”), so that it is computationally difficult to determine a private key from knowledge of its corresponding known public key. The public key can thus be published, for example sent by an unsecured communication or listed in a public registry, to enable data communication data between the holder of the private key and those obtaining the public key, without realistic risk that the private key can be calculated by an attacker. The public/private key approach is generally favored because the holder of the private key need not share that key with any other party; in contrast, symmetric key approaches require both parties to know the same encryption key.
The level of security provided by a particular public key scheme corresponds generally to the length of the keys; longer key lengths increase the difficulty of deriving the private key from the public key. Conventional bit lengths for both public and private keys under such cryptography algorithms as “DH”, “DSA”, and “RSA”, range from on the order of 1024 bits to 15360 bits. Of course, the lengths of the keys can vary widely, depending on the desired security level and the available computational capacity of the encrypting and decrypting nodes.
Elliptic curve cryptography (“ECC”) is a known type of public key cryptography in which the relationship of the public and private keys is based on the algebraic structure of elliptic curves over finite fields. According to this approach, the trap-door function is the solution of a discrete logarithm, over a finite field. This problem is referred to in the art as the “Discrete Logarithm Problem” (in the case of elliptic curves over finite fields, the “Elliptic Curve Discrete Logarithm Problem” or “ECDLP”), and has proven to be more intractable than the problems on which other public key approaches are based. For example, it is believed that a 160-bit ECC private key will provide an equivalent security level as a 1024-bit RSA private key, and that a 512-bit ECC private key will provide an equivalent security level as a 15,360-bit RSA private key. These shorter key lengths of the ECC approach thus greatly reduce the computational cost of the relevant calculations as compared with RSA-like algorithms.
By way of further background, so-called “side-channel” attacks on data security refer to indirect techniques for identifying a private key. However, so-called “side channel” attacks on data communications seek to obtain the private key value by indirect means. Rather than attempting to recover the payload of encrypted data directly (e.g., deriving the private key from the public key by solving the discrete logarithm problem), side channel attacks obtain information about the actions of the decrypting device in carrying out the decryption process, from which the private key can be inferred.
As fundamental in the art, CMOS digital circuits consume power and emit electromagnetic radiation when switching logic states, but consume little power and emit little electromagnetic energy in the steady-state. One type of side-channel attack in the public-private key context is based on measurements of the power consumption of a device over time, obtained either directly or indirectly from associated electromagnetic radiation, as that device performs calculations involving the private key. Relying on the correlation between the power signature and the amount of computational work being carried out, analysis of this power signature allows the attacker to discern the sequence of “1” and “0” bits in the private key. For example, cryptography calculations according to such algorithms as RSA and ECC involve the multiplication of a data value by the private key by adding the data value to itself the number of times indicated by the private key. In the digital context, this operation is carried out by sequentially interrogating the private key value bit-by-bit and executing calculations depending on the value of that bit. For example, each private key bit that is a “1” may cause one sequence of operations to be executed, while each private key bit that is a “0” may cause a different sequence of operations. By sensing the power consumed by the device over the duration of the private key sequence, the side-channel attacker can detect differences in the computational work between the addition and doubling operations, and from those differences can detect the sequence of “1” and “0” bits in the private key value.
FIG. 1 illustrates an example of a detected side-channel signal reflecting the power consumed by a device over time as it decrypts a block data according to the RSA algorithm. In this operation, a squaring and a multiplication are performed for each “1” value in a bit position of the private key, while only a squaring is performed for each “0” bit value. Because, in this conventional example, the multiplication performed for a “1” private key bit involves more device switching (i.e., a greater number of adds) than the squaring operation requires, the detected noise pattern of FIG. 1 exhibits a wider waveform MULT for multiplications than that of waveform SQUA for the squaring operations. As evident in FIG. 1, this allows the multiplication operations to be readily distinguishable from detecting the emitted noise or power consumption. Because the particular algorithms used for decryption are generally well-known, attackers know that each multiplication noise waveform MULT corresponds to the second operation for a “1” bit in the private key. As a result, this side-channel attack readily detects the bit-by-bit digital values of the private key being used to decrypt received data; for example, the noise pattern of FIG. 1 indicates a portion of the private key as 011010 (the private key bits being applied from LSB to MSB). Knowledge of even a portion of the private key can greatly facilitate the identification of the full private key, and thus the ability to clandestinely recover the communicated payload data.
By way of further background, Rondepierre, “Revisiting Atomic Patterns for Scalar Multiplications on Elliptic Curves”, 12th International Conference on Smart Card Research and Advanced Application Conference (CARDIS 2013) (Springer, 2014), pp. 171-86, describes an approach for the protection of elliptic curve scalar multiplications against side-channel analysis, in which doubling and addition are performed so as to have the same computational pattern (i.e., the same side-channel profile). Specifically, the described doubling and addition operations involve eight multiplications, two squaring operations, and ten additions (including subtractions—which have the same computational cost as an addition), all performed in the same order. This article also describes a subtraction operation performed by the same sequence of operations, as may be used in alternative algorithms for finite field scalar multiplication.